翻訳と辞書 Words near each other ・ Perfectionism (psychology) ・ Perfectionist (album) ・ Perfectionist liberalism ・ Perfective aspect ・ Perfectly Clear ・ Perfectly Damaged ・ Perfectly Defect ・ Perfectly Dirty ・ Perfectly Frank ・ Perfectly Good Guitar ・ Perfectly Imperfect ・ Perfectly Imperfect (Sarah Geronimo album) ・ Perfectly matched layer ・ Perfectly Normal ・ Perfectly normal ・ Perfectly orderable graph ・ Perfectly Reasonable Deviations from the Beaten Track ・ Perfectmatch.com ・ Perfecto ・ Perfecto Armijo ・ Perfecto de Castro ・ Perfecto Fluoro ・ Perfecto mobile ・ Perfecto motorcycle jacket ・ Perfecto Para Mi ・ Perfecto Presents Ibiza ・ Perfecto R. Yasay, Jr. ・ Perfecto Records ・ Perfecto V. Fernandez ・ Perfectoid Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Perfectly orderable graph ： ウィキペディア英語版 Perfectly orderable graph In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete. ==Definition== The greedy coloring algorithm, when applied to a given ordering of the vertices of a graph ''G'', considers the vertices of the graph in sequence and assigns each vertex its first available color. Different vertex orderings will lead this algorithm to use different numbers of colorings; there is always an ordering that leads to an optimal coloring (for instance, the ordering determined from an optimal coloring by sorting the vertices by their color has this property) but it may be difficult to find. The perfectly orderable graphs are defined to be the graphs for which there is an ordering that is optimal for the greedy algorithm not just for the graph itself, but for all of its induced subgraphs. More formally, a graph ''G'' is said to be ''perfectly orderable'' if there exists an ordering π of the vertices of ''G'', such that any induced subgraph is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph. An ordering π has this property exactly when there do not exist four vertices ''a'', ''b'', ''c'', and ''d'' for which ''abcd'' is an induced path, ''a'' appears before ''b'' in the ordering, and ''c'' appears after ''d'' in the ordering.〔; .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Perfectly orderable graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.